/*
 *  Optimized version of insertion sort:
 *  1. put smallest element in position as sentinel
 *  2. if array is already sorted, then return
 */
package algs4.sort;

public class InsertionX
{
    /* Static Methods */
    public static void sort(Comparable[] a) {
        int change = 0;
        int n      = a.length;

        // put smallest element in position as sentinel
        Comparable t;
        for (int i = n - 1; i > 0; i--) {
            if (a[i].compareTo(a[i-1]) < 0) {
                t      = a[i];
                a[i]   = a[i-1];
                a[i-1] = t;

                change++;
            }
        }

        // cut off
        if (change == 0) return;

        // insertion sort with sentinel
        for (int i = 2; i < n; i++) {
            int        j = i;
            Comparable v = a[i];

            while (v.compareTo(a[j-1]) < 0) { a[j] = a[j-1]; j--; }

            a[j] = v;
        }
    }

    public static void sort(Comparable[] a, int st, int ed) {
        int change = 0;

        // put smallest element in position as sentinel
        Comparable t;
        for (int i = ed; i > st; i--) {
            if (a[i].compareTo(a[i-1]) < 0) {
                t      = a[i];
                a[i]   = a[i-1];
                a[i-1] = t;

                change++;
            }
        }

        // cut off
        if (change == 0) return;

        for (int i = st + 2; i <= ed; i++) {
            int j = i;
            Comparable v = a[i];

            // insertion sort with sentinel
            while (v.compareTo(a[j-1]) < 0) { a[j] = a[j-1]; j--; }

            a[j] = v;
        }
    }
}
